package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202412;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class leetcode20241215 {
    public int minSetSize(int[] arr){
        Map<Integer,Integer> freq=new HashMap<>();
        for(int x : arr){
            freq.merge(x,1,Integer::sum);// freq[x]++
        }

        List<Integer> cnt=new ArrayList<>(freq.values());
        cnt.sort((a,b)->b-a);

        int s=0;
        for(int i=0;;i++){
            s+=cnt.get(i);
            if(s>=arr.length/2){
                return i+1;
            }
        }
    }
}
